﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_119 : BaseProblem
    {
        public override object GetResult()
        {
            //const long mx = long.MaxValue/10;

            var lst = new List<string>();
            //var lst = new List<long>();
            //var dct = new Dictionary<long, List<long>>();
            //var res = new HashSet<long>();

            for (long a = 2; a <= 200; a++)
            {
                for (long b = 2; b <= 9; b++)
                {
                    var tmp = a.ToString();
                    for (var i = 2; i <= b; i++)
                    {
                        tmp = MathLogic.MultipleString(tmp, a);
                    }
                    if (MathLogic.GetSummOfDigits(tmp) == a)
                        lst.Add(tmp);
                }
            }


            //for (long k = 2; k <= Math.Sqrt(mx); k++)
            //{
            //    long cur = k;
            //    while (true)
            //    {
            //        cur *= k;
            //        if (cur < 10)
            //            continue;
            //        if (cur >= mx / k)
            //            break;
            //        if (!dct.ContainsKey(cur))
            //            dct.Add(cur, new List<long>());
            //        dct[cur].Add(k);
            //        lst.Add(cur);
            //    }
            //}
            //lst.Sort();
            //foreach (var l in lst)
            //{
            //    var q = MathLogic.GetSummOfDigits(l);
            //    if (!dct[l].Contains(q)) continue;
            //    if (res.Contains(l)) continue;
            //    res.Add(l);
            //    if (res.Count == 30)
            //        return l;
            //}
            //return -1;

            for (var i = 0; i < lst.Count - 1; i++)
            {
                for (var j = i + 1; j < lst.Count; j++)
                {
                    if (MathLogic.IsGreat(lst[i], lst[j]))
                    {
                        var qq = lst[i];
                        lst[i] = lst[j];
                        lst[j] = qq;
                    }
                }
            }
            return lst[29];
        }

        public override string Problem
        {
            get
            {
                return @"The number 512 is interesting because it is equal to the sum of its digits raised to some power: 5 + 1 + 2 = 8, and 83 = 512. Another example of a number with this property is 614656 = 284.

We shall define an to be the nth term of this sequence and insist that a number must contain at least two digits to have a sum.

You are given that a2 = 512 and a10 = 614656.

Find a30.";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return "248155780267521";
            }
        }
    }
}
